1289. 下降路径最小和 II

Similar Question

Solution Tips

方案一: Dfs

var minFallingPathSum = function(grid) {
    // 特殊的路径和
    // grid 最大能到 99, 直接回溯很可能会超时的
    // 可以简化为 N 叉树的 路径 最小和, 因为是整条路径的, 所以不需要前缀和的思路
    // 可以优化一下, 对于第 row 行的来说, 选择 !col 外的最小肯定是最优的
    // 求出每一行的最优解, 然后下一行继续参考上一行的, 动态规划的思路

    // 如果只有一行, 直接返回最小值即可
    if (grid.length === 1) {
        return Math.min(...grid[0]);
    }

    let min = Number.MAX_SAFE_INTEGER;
    for (let i = 0; i < grid[0].length; i++) {
        dfs(0, i, 0);
    }
    return min;

    function dfs(row, col, curSum) {
        if (row === grid.length) {
            // 递归到最底部了, 按理说这里直接取 curSum 就可以
            min = Math.min(min, curSum);
            return;
        }

        // 累加当前路径和
        curSum += grid[row][col];
        // 继续递归累加路径和
        for (let i = 0; i < grid[0].length; i++) {
            if (i !== col) {
                dfs(row + 1, i, curSum);
            }
        }
    }
};

方案二: 动态规划

var minFallingPathSum = function(grid) {
    // 特殊的路径和
    // grid 最大能到 99, 直接回溯很可能会超时的
    // 可以简化为 N 叉树的 路径 最小和, 因为是整条路径的, 所以不需要前缀和的思路
    // 可以优化一下, 对于第 row 行的来说, 选择 !col 外的最小肯定是最优的
    // 求出每一行的最优解, 然后下一行继续参考上一行的, 动态规划的思路

    // 如果只有一行, 直接返回最小值即可
    if (grid.length === 1) {
        return Math.min(...grid[0]);
    }

    // 定义dp[i][j] 为第 i 行 第 j 列的下降路径最小和
    const dp = Array.from({ length: grid.length }, () => new Array(grid[0].length).fill(Number.MAX_SAFE_INTEGER));

    // 构造负1行
    dp[-1] = [];
    for (let i = 0; i < grid[0].length; i++) {
        dp[-1][i] = 0;
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            // 等于上一行中, 除了 j 以外的最小的
            let prevRowMin = Number.MAX_SAFE_INTEGER;
            for (let k = 0; k < grid[0].length; k++) {
                if (k !== j) {
                    prevRowMin = Math.min(prevRowMin, dp[i - 1][k]);
                }
            }
            dp[i][j] = prevRowMin + grid[i][j];
        }
        // TODO: 构造一个数组, 每一行除了自身以外最小的, 意义不大, 只是找最小的位置换了而已
        console.log(dp[i])
    }

    // 最后一行中最小的即是答案
    return Math.min(...dp[dp.length - 1]);
};

// console.log(minFallingPathSum([[1,2,3],[4,5,6],[7,8,9]]));
console.log(minFallingPathSum([[-73,61,43,-48,-36],[3,30,27,57,10],[96,-76,84,59,-15],[5,-49,76,31,-7],[97,91,61,-46,67]]));

方案三: 动态规划优化

var minFallingPathSum = function(grid) {
    const n = grid.length;
    let first_min_sum = 0, second_min_sum = 0;
    let first_min_index = -1;
    
    for (let i = 0; i < n; i++) {
        let cur_first_min_sum = Infinity, cur_second_min_sum = Infinity;
        let cur_first_min_index = -1;
        
        for (let j = 0; j < n; j++) {
            let cur_sum = grid[i][j];
            if (j != first_min_index) {
                cur_sum += first_min_sum;
            } else {
                cur_sum += second_min_sum;
            }
            if (cur_sum < cur_first_min_sum) {
                cur_second_min_sum = cur_first_min_sum;
                cur_first_min_sum = cur_sum;
                cur_first_min_index = j
            } else if (cur_sum < cur_second_min_sum) {
                cur_second_min_sum = cur_sum;
            }
        }
        first_min_sum = cur_first_min_sum;
        second_min_sum = cur_second_min_sum;
        first_min_index = cur_first_min_index;
    }
    return first_min_sum;
};